// https://leetcode.cn/problems/integer-replacement/description/

// 算法思路总结：
// 1. 贪心策略处理整数替换问题
// 2. 偶数直接除以2，奇数选择更优操作
// 3. 通过模4判断选择加1或减1操作
// 4. 特殊情况n=3需要单独处理
// 5. 时间复杂度：O(log n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int integerReplacement(int n) 
    {
        if (n == 1) return 0;
        if (n == 3) return 2;

        int ret = 0;
        while (n > 1)
        {
            if (n % 2 == 0)
            {
                ret++;
                n /= 2;
            }
            else
            {
                if (n == 3)
                {
                    ret += 2;
                    n = 1;
                }
                else if (n % 4 == 1)
                {
                    ret += 2;
                    n /= 2;
                }
                else
                {
                    ret += 2;
                    n = n / 2 + 1;
                }
            }
        }

        return ret;
    }
};

int main()
{
    int n1 = 8, n2 = 7;
    Solution sol;

    cout << sol.integerReplacement(n1) << endl;
    cout << sol.integerReplacement(n2) << endl;

    return 0;
}